/**
 * @file
 * Binary Tree basic functions
 */

#ifndef __TREE_H
#define __TREE_H

#ifndef __UTIL_H
# error "Please include util.h before tree.h"
#endif

struct tree_node {
  struct tree_node *lc, *rc, *pn;
};

#define parent(n)                               \
  ((n)->pn)

#define set_parent(n, p)                        \
  ((n)->pn = p)

#define left(n)                                 \
  ((n)->lc)

#define set_left(p,c)                           \
  ((p)->lc = c)

#define right(n)                                \
  ((n)->rc)

#define set_right(p, c)                         \
  ((p)->rc = c)

#define is_leaf(n)                              \
  (!(n))

#define is_root(n)                              \
  (!parent(n))

#define is_child_left(n)                        \
  ((n) == left(parent(n)))

#define is_child_right(n)                       \
  ((n) == right(parent(n)))

#define grandparent(n)                          \
  (!parent(n) ? NULL : parent(parent(n)))

#define uncle(n)                                                        \
  (!grandparent(n) ? NULL : is_child_left(parent(n)) ? right(grandparent(n)) : left(grandparent(n)))

#define sibling(n)                                                      \
  (!parent(n) ? NULL : is_child_left(n) ? right(parent(n)) : left(parent(n)))

#define INIT_TREE_NODE(n) do {                  \
      set_left(n, NULL);                        \
      set_right(n, NULL);                       \
      set_parent(n, NULL);                      \
  } while(0)

#define TREE_NODE_INIT(n)                       \
  { NULL, NULL, NULL }

#define tree_entry(n, type, member)             \
  (!(n) ? NULL : get_super_struct(n, type, member))

inline void xchg_node(struct tree_node *n1, struct tree_node *n2);

#endif /* __TREE_H */
